package 对递归问题的分析.day01;

import leecode.二叉树.TreeNode;

/**
 * @author wangxi created on 2024/8/18 23:45
 * @version v1.0
 * https://leetcode.cn/problems/balanced-binary-tree/
 *
 * 平衡二叉树：左右子树节点高度差值<=1，高度代表该节点的最大深度
 */
public class AVL2 {
    public static void main(String[] args) {

    }

    boolean flag = true;
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        help(root);
        return flag;
    }

    // 自顶向下
    private void help(TreeNode root) {
        if (root == null) {
            return;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        if (!flag) {
            return;
        }
        if (Math.abs((left - right)) > 1) {
            flag = false;
            return;
        }
        help(root.left);
        help(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        return left >= right ? left + 1 : right + 1;
    }
}
